package 算法.tanxin;

import java.util.HashMap;

/**
 * @author lchenglong
 * @date 2022/3/5
 */
public class LRUCache2 {

    private Integer capacity;
    private Node head;
    private Node tail;

    private HashMap<Integer,Node> map;

    public LRUCache2(Integer capacity) {
        this.capacity = capacity;
        map = new HashMap<Integer, Node>(capacity);
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            if (map.size() >= capacity) {
                // 容量超过的时候移除头结点
                int removedKey = head.key;
                removeNode(head);
                map.remove(removedKey);
            }
            node = new Node(key, value);
            addNode(node);
            map.put(key, node);
        } else {
            node.value = value;
            refreshNode(node);
        }
    }

    /**
     * 查询节点
     *
     * @param key
     * @return
     */
    public Integer get(Integer key){
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 访问后的节点放到最后
        refreshNode(node);
        return node.value;
    }

    /**
     * 刷新节点到尾节点
     * @param node
     */
    private void refreshNode(Node node) {
        if (node == tail) {
            // 已经是尾结点 则忽略
            return;
        }
        // 将节点放到尾节点
        removeNode(node);
        addNode(node);
    }


    /**
     * 新增节点
     * @param node
     */
    private void addNode(Node node) {
        if (tail == null) {
            // 新增第一个节点
            head = node;
            tail = node;
        } else {
            // 增加到尾节点
            tail.next = node;
            node.pre = tail;
            tail = tail.next;
        }
    }

    /**
     * 移除节点
     * @param node
     */
    private void removeNode(Node node) {
        if (node == head && node == tail) {
            // 只有一个节点的时候的移除
            head = null;
            tail = null;
        } else if (node == tail) {
            //移除尾结点
            tail = tail.pre;
            tail.next = null;
        } else if (node == head) {
            // 移除头节点
            head = head.next;
            head.pre = null;
        } else {
            // 移除其他节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
    }


    /**
     * LRU节点
     */
    class Node{
            int key;
            int value;
            Node pre;
            Node next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
    }



    public static void main(String[] args) {
        LRUCache2 cache = new LRUCache2( 2 /* capacity */ );
        cache.put(1, 1);
        cache.put(2, 2);
        int value = cache.get(1); // returns 1
        cache.put(3, 3); // evicts key 2
        value = cache.get(2); // returns -1 (not found)
        cache.put(4, 4); // evicts key 1
        value = cache.get(1); // returns -1 (not found)
        value = cache.get(3); // returns 3
        value = cache.get(4); // returns 4
    }
}
